package 哈希表;

import java.util.*;



class Student implements Comparable<Student>{
    private String id;

    public Student(String id) {
        this.id = id;
    }
    public Student() {
    }

    @Override
    public String toString() {
        return "Student{" +
                "id='" + id + '\'' +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return Objects.equals(id, student.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }

    @Override
    public int compareTo(Student o) {
        return 0;
    }
}
public class Test {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public static void func(String s1,String s2) {
        Set<Character> set1 = new HashSet<>();
        Set<Character> set2 = new HashSet<>();
        for (int i = 0; i < s2.length(); i++) {
            char ch = Character.toUpperCase(s2.charAt(i));
            set1.add(ch);
        }
        for (int i = 0; i < s1.length(); i++) {
            char ch = Character.toUpperCase(s1.charAt(i));
            if(!set1.contains(ch) && !set2.contains(ch)) {
                set2.add(ch);
                System.out.print(ch);
            }
        }

    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNextLine()) {
            String str1 = scan.nextLine();
            String str2 = scan.nextLine();
            func(str1,str2);
        }
    }
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            map.put(cur,new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
        }
        return map.get(head);
    }
    public static void main12(String[] args){
        Object o=new Object(){
            public boolean equals(Object obj){
                return true;
            }
        };
        System.out.println(o.equals("“Fred”"));
    }
    public static void main11(String[] args) {
 //       int i=500;
        Integer i = 127;
        Integer j = 127;
        System.out.println(i==j);
        System.out.println(j.equals(i));
    }
    public int singleNumber1(int[] array) {
        Map<Integer,Integer> map = new HashMap();
        for (int i = 0; i < array.length; i++) {
            map.put(array[i],map.getOrDefault(array[i],0)+1 );
        }
        for (int i = 0; i < array.length; i++) {
           if(map.get(array[i]) == 1) {
               return array[i];
           }
        }
        return -1;
    }

        public int singleNumber(int[] array) {
        Map<Integer,Integer> map = new HashMap();
        for (int i = 0; i < array.length; i++) {
            map.put(array[i],map.getOrDefault(array[i],0)+1 );
        }
        for (Map.Entry<Integer,Integer> x: map.entrySet()) {
            if(x.getValue() == 1) {
           return x.getKey();
            }
        }
        return -1;
    }
    public static void main9(String[] args) {
        int[] array ={6,5,9,3,3,5,2,8,78,3};
        Map<Integer,Integer> map = new HashMap();
        for (int i = 0; i < array.length; i++) {
            map.put(array[i],map.getOrDefault(array[i],0)+1 );
        }
        for (Map.Entry<Integer,Integer> x: map.entrySet()) {
            if(x.getValue() >= 2) {
                System.out.println(x);
            }
        }
    }
    public static void main8(String[] args) {
        int[] array ={6,5,9,3,3,5,2,8,78,3};
        Map<Integer,Integer> map = new HashMap();
        for (int i = 0; i < array.length; i++) {
            map.put(array[i],map.getOrDefault(array[i],0)+1 );
        }
        int size = 0;
        for (int i = 0; i < array.length; i++) {
            if(map.getOrDefault(array[i],0) >= 2){
                size++;
                map.remove(array[i]);
            }
        }
        System.out.println(size);
    }
    public static void main7(String[] args) {
        int[] array ={6,5,9,3,3,5,2,8,78,3};
        Map<Integer,Integer> map = new HashMap();
        for (int i = 0; i < array.length; i++) {
            map.put(array[i],map.getOrDefault(array[i],0)+1 );
        }
        Set<Map.Entry<Integer,Integer>> set =  map.entrySet();
        System.out.println(set);
    }
    public static void main6(String[] args) {
        //找到第一个重复的数据
        int[] array ={6,5,9,3,3,5,2,8,78,3};
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            if(!set.contains(array[i])) {
                set.add(array[i]);
            }else {
                System.out.println(array[i]);
                break;
            }
        }
    }
    public static void main5(String[] args) {
        //找到第一个重复的数据
        int[] array ={6,5,9,3,3,5,2,8,78,3};
        Map<Integer,Integer> map = new HashMap();
        for (int i = 0; i < array.length; i++) {
            map.put(array[i],map.getOrDefault(array[i],0)+1 );
        }
        for (int i = 0; i < array.length; i++) {
            if(map.get(array[i]) != 1){
                System.out.println(array[i]);
            break;
            }
        }
    }
    public static void main4(String[] args) {
        //去重
        int[] array ={3,3,5,6,2,8,78,3};
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i <array.length ; i++) {
            set.add(array[i]);
        }
        System.out.println(set);
    }
    public static void main3(String[] args) {
        HashBuckPlus<Student,String> hash = new HashBuckPlus<>();
        Student st1 =new Student("123456");
        System.out.println(st1.hashCode());
        Student st2 =new Student("123456");
        System.out.println(st2.hashCode());
        hash.put(st1,"武毅");
        hash.put(st2,"王五");
        System.out.println();
    }
    public static void main2(String[] args) {
        Student st1 =new Student("123456");
        System.out.println(st1.hashCode());
        Student st2 =new Student("123456");
        System.out.println(st2.hashCode());
    }
    public static void main1(String[] args) {
        HashBuck hashBuck =new HashBuck();
        hashBuck.put(1,11);
        hashBuck.put(2,22);
        hashBuck.put(5,55);
        hashBuck.put(3,33);
        hashBuck.put(4,44);
        hashBuck.put(5,55);
        hashBuck.put(6,66);
        hashBuck.put(7,77);
        hashBuck.put(8,88);
        hashBuck.put(15,521);

        Integer val = hashBuck.get(8);
        System.out.println(val);
    }
    //宝石与石头
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        for (char x: jewels.toCharArray()) {
            set.add(x);
        }
        int count = 0;
        for (char x: stones.toCharArray()) {
            if(set.contains(x)) {
                count++;
            }
        }
        return count;
    }
}
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
class Solution {
    public TreeNode Convert(TreeNode root) {
        //那就中序遍历
        //非递归中序遍历
        //中序遍历一个一个放入map
        Map<Integer,TreeNode> map = new HashMap<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        int size = 0;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
                if(cur == null) {
                    break;
                }
            }
            TreeNode prev = stack.pop();
            map.put(size++,prev);
            System.out.println(prev.val);
            cur = prev.right;
        }
        for (int i = 0; i < size; i++) {
            if(i == 0){
                map.get(i).left = null;
            }else {
                map.get(i).left = map.get(i-1);
            }
            if(i+1 == size) {
                map.get(i).right = null;
            }else {
                map.get(i).right = map.get(i+1);
            }
        }
        return map.get(0);
    }
    public static void func(String s1,String s2) {
        Set<Character> set1 = new HashSet<>();
        Set<Character> set2 = new HashSet<>();
        for (char x:s2.toUpperCase().toCharArray()) {
            set1.add(x);
        }
        for (char x:s1.toUpperCase().toCharArray()) {
            if(!set1.contains(x) && !set2.contains(x)) {
                set2.add(x);
                System.out.print(x);
            }
        }

    }
    //找出前k个高频单词
    //由大到小排序
    //出现次数一样按字典序排序

    public List<String> topKFrequent(String[] words, int k) {
        //定义一个map
        Map<String,Integer> map = new HashMap<>();
        //先都放入map里面
        for (String x: words) {
            //如果有返回当前的val
            //如果没有就返回0
            map.put(x,map.getOrDefault(x,0)+1);
        }
        //建立小根堆
        PriorityQueue<Map.Entry<String,Integer>> pri = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                //按照次数排序
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    //如果次数相等就按照字典序排序
                    return o2.getKey().compareTo(o1.getKey());
                }
                //如果次数比相等就按照次数排序
                return o1.getValue().compareTo(o2.getValue());
                //次数从小到大，字典序从大到小，翻转就是 次数从大到小，字典序从小到大
            }
        });
        //遍历hashmap把里面的数据放到小根堆
        //重点
        for (Map.Entry<String,Integer> entry: map.entrySet()) {
            if(pri.size() < k) {
                pri.offer(entry);
            }else {
                //堆顶的频率小于当前的频率就出队，否则就入队
                //如果频率相等时，就按照字典序比较
                if(pri.peek().getValue().compareTo(entry.getValue()) == 0) {
                    //如果当前字典序大于根，那就弹出字典序大的，将字典序小的入进来
                    if(pri.peek().getKey().compareTo(entry.getKey()) > 0) {
                        pri.poll();
                        pri.offer(entry);
                    }
                }else if(pri.peek().getValue().compareTo(entry.getValue()) < 0) {
                    pri.poll();
                    pri.offer(entry);
                }
            }
        }
        //此时小根堆已经有了频率从大到小的结果
        //定一个集合然后翻转该集合
       List<String> list = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            list.add(pri.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }
}